package com.Shuang.Demo6;

import java.util.*;

//让泛型类E继承Comparable接口，使后面泛型类用Collections默认排序知道规则
public class MyLinkedList<E extends Comparable> {
    // 封装一个链表
    Node<E> head = null;
    /**
     * 定义了一个私有的内部类，作为链表的结点。
     */
    public static class Node<E> {
        E data;
        Node<E> next;

        public Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }

    public Node<E> add(E e) {
        if (head == null) {
            head = new Node(e, null);
        } else {
            // 往后面插入结点。（尾插法）
            Node<E> temp = head;
            // 让temp走到尾部结点
            while (temp.next != null) {
                temp = temp.next;
            }
            // 把当前结点创建出来，加入到尾部结点
            temp.next = new Node(e, null);
        }
        return head;
    }

    //将链表升序排序
    public Node<E> sort(){

        if (head == null){
            return head;
        }

        //将链表数据遍历出来放到集合中排序 再把链表重新连起来
        List<E> linkList = new ArrayList<>();
        //保存头节点
        Node<E> temp1 = head;
        //遍历头节点数据加到集合中去
        while (temp1 != null){
            E data = temp1.data;
            linkList.add(data);
            temp1 = temp1.next;
        }

        Collections.sort(linkList);

        Node<E> temp2 = head;
        //遍历集合中排好序的数据，重新连接链表
        for (E e : linkList) {
            temp2.data = e;
            temp2 = temp2.next;
        }
        return head;
    }

    //遍历链表打印数据
    public void forEach(){
        if (head == null){
            System.out.println(head);
            return;
        }
        Node<E> temp = head;
        while (temp != null){
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    //支持将这两个升序排序的链表，再次合并成一个新链表，要求新链表中的节点仍然是递增排序的
    //用第一个链表调用将第二个链表传进来合并 排序
    public Node<E> mergeSort(Node<E> head2){

        if (head == null && head2 == null){
            return null;
        }

        if (head != null && head2 == null){
            return head;
        }

        if (head == null && head2 != null){
            return head2;
        }

        if (head != null && head2 != null){
            //将链表1进行遍历到尾节点然后连接上链表2，然后调用排序排一下序
            Node<E> temp1 = head;
            while (temp1.next != null){
                temp1 = temp1.next;
            }
            temp1.next = head2;
            sort();
        }
        return head;
    }

}